// https://www.lintcode.com/problem/subarray-sum/description

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        map<int, int> record_map;
        int sum = 0;
        vector<int> result;
        record_map[0] = -1; // 输入为单个0
        for (int i = 0; i < nums.size(); ++i)
        {
            sum += nums[i];
            if (record_map.find(sum) != record_map.end())
            {
                result.push_back(record_map[sum] + 1); // 注意要加1
                result.push_back(i); 
                return result;
            }
            record_map[sum] = i;
        }
        return result;
    }
};